package com.lfg.leetcode.leetcode100;


public class No162findPeakElement {

    public static void main(String[] args) {
        int ret = findPeakElement(new int[]{1, 2, 3, 4});
        System.out.println(ret);
    }

    public static int findPeakElement(int[] nums) {
        if (nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        Integer ret = findPeakElement(nums, 0, nums.length - 1);
        if (null == ret) {
            return Integer.MIN_VALUE;
        }
        return ret;
    }

    public static Integer findPeakElement(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int total = start + end;
        int mid = total / 2;
        if ((total & 1) == 1) {
            mid += 1;
        }
        if (mid < nums.length - 1 && nums[mid] <= nums[mid + 1]) {
            return findNext(nums, start, end, mid);
        }
        if (mid > 0 && nums[mid - 1] >= nums[mid]) {
            return findNext(nums, start, end, mid);
        }
        return mid;
    }

    private static Integer findNext(int[] nums, int start, int end, int mid) {
        if (start == end) {
            return null;
        }
        Integer left = findPeakElement(nums, start, mid - 1);
        if (null != left) {
            return left;
        }
        Integer right = findPeakElement(nums, mid + 1, end);
        if (null != right) {
            return right;
        }
        return null;
    }
}
